﻿//希尔排序（简化代码）
//void ShellSort(int* a, int n) {
//	int grep = n;
//	while (grep > 1) {
//		grep = grep / 3 + 1;
//		for (int i = 0; i < n - grep; i++) {
//			int end = a[i + grep];
//			int j = i;
//			while (j >= 0 && a[j] > end) {
//				a[j + grep] = a[j];
//				j -= grep;
//			}
//			a[j + grep] = end;
//		}
//	}
//}

//三数取中进阶版，保证开头元素不在有序序列的位置,即尽量使begin位置上的元素不是最小或最大。
//void GetMiddleData(int* a, int begin, int end) {
//	int middle = (begin + end) / 2;
//	if (a[begin] > a[middle]) {
//		if (a[end] < a[middle]) {
//			Swap(a + begin, a + middle);
//		}
//		else if (a[end] > a[begin]) {
//			return;
//		}
//		else {
//			Swap(a + begin, a + middle);
//		}
//	}
//	else {
//		if (a[end] > a[middle]) {
//			Swap(a + begin, a + middle);
//		}
//		else if (a[end] < a[begin]) {
//			return;
//		}
//		else {
//			Swap(a + begin, a + middle);
//		}
//	}
//}

//练习
//int QuickPart1(int* a, int begin, int end) {
//	GetMiddleData(a, begin, end);
//	int x = begin;
//	while (begin < end) {
//		while (begin < end && a[end] >= a[x]) {
//			end--;
//		}
//		while (begin < end && a[begin] <= a[x]) {
//			begin++;
//		}
//		Swap(a + begin, a + end);
//	}
//	Swap(a + begin, a + x);
//	return begin;
//}
//int QuickPart2(int* a, int begin, int end) {
//	GetMiddleData(a, begin, end);
//	int hole = begin;
//	int x = a[begin];
//	while (begin < end) {
//		while (begin < end && a[end] >= x) {
//			end--;
//		}
//		a[hole] = a[end];
//		hole = end;
//		while (begin < end && a[begin] <= x) {
//			begin++;
//		}
//		a[hole] = a[begin];
//		hole = begin;
//	}
//	a[hole] = x;
//	return hole;
//}